#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, a[100005], sum;
const int p = 111121;
long long qpow(long long a, long long b) {
	if (a == 0 && b == 0) return 0;
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
vector<int> edges[100005];

void dfs(int rt, int i, int lor, int land, int fa = -1) {
	if (i <= rt) sum += qpow(land, lor);
	for (auto j : edges[i]) {
		if (j != fa) {
			dfs(rt, j, (lor | a[j]), (land & a[j]), i);
		}
	}
}

signed main() {
	freopen("abstract.in", "r", stdin); freopen("abstract.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	if (n <= 5000) {
		for (int i = 1; i <= n; ++i) {
			dfs(i, i, a[i], a[i]);
		}
	}
	cout << sum % p;
	return 0;
}
